package com.hanxiaozhang.no10leetcode.array;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给一个正整数数组，假设你的初始位置是数组中的第一位，数组中的每个元素代表了你当前所能跳跃的最大值，
 * 你的目标是用最少的跳跃次数跳到数组的最后一位。你可以认为你一定能够到达最后一位。
 * 实例:
 * 输入: [2,3,1,1,4]
 * 输出: 2
 * 先跳一步，再跳三步，最少跳两次到达。
 * <p>
 * 思路：
 * 1. 声明最远距离变量（farthest） 声明每次的跳的最远位置变量（end） 声明次数（times）
 * 2. 循环每次计算当前位置最远距离  -> Math.max(farthest, i + nums[i])
 * 3. 最远距离 大于 数组长度 -1（终点），证明成功跳过，结束循环
 * 4. 判断 i == end
 * <p>
 * <p>
 * 有问题
 *
 * @author hanxinghua
 * @create 2024/1/15
 * @since 1.0.0
 */
public class No45JumpGameII {

    public static void main(String[] args) {

        int[] nums = {2, 3, 1, 1, 4};
        ///int[] nums = {2, 3, 0, 1, 4};
        // int[] nums = {2, 1};
        // int[] nums = {1};

        System.out.println(method1(nums));
        System.out.println(method2(nums));

    }

    /**
     * 方法1
     * Tips：你可以认为你一定能够到达最后一位。
     *
     * @param nums
     * @return
     */
    public static int method1(int[] nums) {

        if (nums.length == 1) {
            return 0;
        }
        // 最远位置
        int farthest = 0;
        // 每次的跳的最远位置
        int end = 0;
        // 次数
        int times = 0;
        for (int i = 0; i < nums.length; i++) {

            farthest = Math.max(farthest, i + nums[i]);

            // 最远距离 大于 数组长度 -1（终点） ，证明成功跳过
            // -> 举例：数组长度为4时，只需要跳三步就到终点了。
            if (farthest > nums.length - 1) {
                if (times == 0) {
                    times++;
                }
                break;
            }

            // 第一次时（i=0，end=0）。i==end成立，times++ end=farthest
            // 第二次时 ...
            if (i == end) {
                times++;
                end = farthest;
            }
        }
        return times;
    }


    /**
     * 方法2
     * <p>
     * 如果某一个起跳点的格式可以跳跃的距离是3，表示后面3个格子都可以作为起跳点。
     * 如果从这个起跳点叫做第1次跳跃，后面3个格子起跳都叫做第2次跳跃。
     * 所以，当一次跳跃结束时，从下一个格子开始，到现在能跳到的最远的距离，都是下一次跳跃的起跳点。
     * <p>
     * - 对每一次跳跃，用for循环来模拟。
     * - 跳完一次之后，更新下一次起跳点的范围。
     * - 在新的范围内跳，更新能跳到最远的距离。
     * 记录跳跃次数，如果跳到了终点，就得到了结果。
     *
     * @param nums
     * @return
     */
    private static int method2(int[] nums) {

        // 开始位置，结束位置 跳跃次数
        int begin = 0, end = 0, times = 0;

        // 模拟每次跳跃，控制条件：结束位置 < 数组数量
        while (end < nums.length - 1) {
            int temp = 0;
            // 模拟当前可跳跃步长内，最远距离。
            for (int i = begin; i <= end; i++) {
                temp = Math.max(nums[i] + i, temp);
            }
            // 下一次起跳点范围开始的格子
            begin = end + 1;
            // 下一次[起跳点]范围结束的格子
            end = temp;
            // 跳跃次数
            ++times;
        }
        return times;

    }

}
